home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 14 / CU Amiga Magazine's Super CD-ROM 14 (1997)(EMAP Images)(GB)(Track 1 of 3)[!][issue 1997-09].iso / CUCD / Programming / Mesa-2.2 / src-glu / tesselat.c < prev   
Encoding:
C/C++ Source or Header  |  1997-02-17  |  9.5 KB  |  444 lines
  1. /* $Id: tesselat.c,v 1.3 1997/02/17 17:24:58 brianp Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  2.2
  6.  * Copyright (C) 1995-1997  Brian Paul
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25.  * $Log: tesselat.c,v $
  26.  * Revision 1.3  1997/02/17 17:24:58  brianp
  27.  * more tesselation changes (Randy Frank)
  28.  *
  29.  * Revision 1.2  1997/02/13 18:31:57  brianp
  30.  * fixed some numerical precision problems (Randy Frank)
  31.  *
  32.  * Revision 1.1  1996/09/27 01:19:39  brianp
  33.  * Initial revision
  34.  *
  35.  */
  36.  
  37.  
  38. /*
  39.  * This file is part of the polygon tesselation code contributed by
  40.  * Bogdan Sikorski
  41.  */
  42.  
  43.  
  44. #include <stdlib.h>
  45. #include <math.h>
  46. #include "tess.h"
  47.  
  48.  
  49.  
  50. static GLboolean edge_flag;
  51.  
  52. static void emit_triangle(GLUtriangulatorObj *, tess_vertex *,
  53.     tess_vertex *,tess_vertex *);
  54.  
  55. static void emit_triangle_with_edge_flag(GLUtriangulatorObj *,
  56.      tess_vertex *,GLboolean,tess_vertex *,GLboolean,
  57.      tess_vertex *,GLboolean);
  58.  
  59. static GLdouble twice_the_triangle_area(
  60.     tess_vertex *va,
  61.     tess_vertex *vb,
  62.     tess_vertex *vc)
  63. {
  64.     return     (vb->x - va->x)*(vc->y - va->y) - (vb->y - va->y)*(vc->x - va->x);
  65. }
  66.  
  67. static GLboolean left(
  68.     GLdouble A,
  69.     GLdouble B,
  70.     GLdouble C,
  71.     GLdouble x,
  72.     GLdouble y)
  73. {
  74.     if(A*x+B*y+C > -EPSILON)
  75.         return GL_TRUE;
  76.     else
  77.         return GL_FALSE;
  78. }
  79.  
  80. static GLboolean right(
  81.     GLdouble A,
  82.     GLdouble B,
  83.     GLdouble C,
  84.     GLdouble x,
  85.     GLdouble y)
  86. {
  87.     if(A*x+B*y+C < EPSILON)
  88.         return GL_TRUE;
  89.     else
  90.         return GL_FALSE;
  91. }
  92.  
  93. static GLint convex_ccw(
  94.     tess_vertex *va,
  95.     tess_vertex *vb,
  96.     tess_vertex *vc,
  97.     GLUtriangulatorObj *tobj)
  98. {
  99.     GLdouble    d;
  100.  
  101.     d = twice_the_triangle_area(va,vb,vc);
  102.  
  103.     if (d > EPSILON ) {
  104.         return 1;
  105.     } else if (d < -EPSILON ) {
  106.         return 0;
  107.     } else {
  108.         return -1;
  109.     }
  110. }
  111.  
  112. static GLint convex_cw(
  113.     tess_vertex *va,
  114.     tess_vertex *vb,
  115.     tess_vertex *vc,
  116.     GLUtriangulatorObj *tobj)
  117. {
  118.     GLdouble    d;
  119.  
  120.     d = twice_the_triangle_area(va,vb,vc);
  121.  
  122.     if (d < -EPSILON ) {
  123.         return 1;
  124.     } else if (d > EPSILON ) {
  125.         return 0;
  126.     } else {
  127.         return -1;
  128.     }
  129. }
  130.  
  131. static GLboolean diagonal_ccw(
  132.     tess_vertex *va,
  133.     tess_vertex *vb,
  134.     GLUtriangulatorObj *tobj,
  135.     tess_contour *contour)
  136. {
  137.     tess_vertex *vc=va->next , *vertex , *shadow_vertex;
  138.     struct
  139.     {
  140.         GLdouble A,B,C;
  141.     } ac,cb,ba;
  142.     GLdouble x,y;
  143.  
  144.     GLint     res = convex_ccw(va,vc,vb,tobj);
  145.     if (res == 0) return GL_FALSE;
  146.     if (res == -1) return GL_TRUE;
  147.  
  148.     ba.A=vb->y - va->y;
  149.     ba.B=va->x - vb->x;
  150.     ba.C= -ba.A*va->x - ba.B*va->y;
  151.     ac.A=va->y - vc->y;
  152.     ac.B=vc->x - va->x;
  153.     ac.C= -ac.A*vc->x - ac.B*vc->y;
  154.     cb.A=vc->y - vb->y;
  155.     cb.B=vb->x - vc->x;
  156.     cb.C= -cb.A*vb->x - cb.B*vb->y;
  157.     for(vertex=vb->next;vertex!=va;vertex=vertex->next)
  158.     {
  159.         shadow_vertex=vertex->shadow_vertex;
  160.         if(shadow_vertex!=NULL && 
  161.             (shadow_vertex==va || shadow_vertex==vb || shadow_vertex==vc))
  162.             continue;
  163.         x=vertex->x;
  164.         y=vertex->y;
  165.         if(left(ba.A,ba.B,ba.C,x,y) &&
  166.             left(ac.A,ac.B,ac.C,x,y) &&
  167.             left(cb.A,cb.B,cb.C,x,y))
  168.             return GL_FALSE;
  169.     }
  170.     return GL_TRUE;
  171. }
  172.  
  173. static GLboolean diagonal_cw(
  174.     tess_vertex *va,
  175.     tess_vertex *vb,
  176.     GLUtriangulatorObj *tobj,
  177.     tess_contour *contour)
  178. {
  179.     tess_vertex *vc=va->next , *vertex , *shadow_vertex;
  180.     struct
  181.     {
  182.         GLdouble A,B,C;
  183.     } ac,cb,ba;
  184.     GLdouble x,y;
  185.  
  186.     GLint     res = convex_cw(va,vc,vb,tobj);
  187.     if (res == 0) return GL_FALSE;
  188.     if (res == -1) return GL_TRUE;
  189.  
  190.     ba.A=vb->y - va->y;
  191.     ba.B=va->x - vb->x;
  192.     ba.C= -ba.A*va->x - ba.B*va->y;
  193.     ac.A=va->y - vc->y;
  194.     ac.B=vc->x - va->x;
  195.     ac.C= -ac.A*vc->x - ac.B*vc->y;
  196.     cb.A=vc->y - vb->y;
  197.     cb.B=vb->x - vc->x;
  198.     cb.C= -cb.A*vb->x - cb.B*vb->y;
  199.     for(vertex=vb->next;vertex!=va;vertex=vertex->next)
  200.     {
  201.         shadow_vertex=vertex->shadow_vertex;
  202.         if(shadow_vertex!=NULL && 
  203.             (shadow_vertex==va || shadow_vertex==vb || shadow_vertex==vc))
  204.             continue;
  205.         x=vertex->x;
  206.         y=vertex->y;
  207.         if(right(ba.A,ba.B,ba.C,x,y) &&
  208.             right(ac.A,ac.B,ac.C,x,y) &&
  209.             right(cb.A,cb.B,cb.C,x,y))
  210.             return GL_FALSE;
  211.     }
  212.     return GL_TRUE;
  213. }
  214.  
  215. static void clip_ear(
  216.     GLUtriangulatorObj *tobj,
  217.     tess_vertex *v,
  218.     tess_contour *contour)
  219. {
  220.     emit_triangle(tobj,v->previous,v,v->next);
  221.     /* the first in the list */
  222.     if(contour->vertices==v)
  223.     {
  224.         contour->vertices=v->next;
  225.         contour->last_vertex->next=v->next;
  226.         v->next->previous=contour->last_vertex;
  227.     }
  228.     else
  229.     /* the last ? */
  230.     if(contour->last_vertex==v)
  231.     {
  232.         contour->vertices->previous=v->previous;
  233.         v->previous->next=v->next;
  234.         contour->last_vertex=v->previous;
  235.     }
  236.     else
  237.     {
  238.         v->next->previous=v->previous;
  239.         v->previous->next=v->next;
  240.     }
  241.     free(v);
  242.     --(contour->vertex_cnt);
  243. }
  244.  
  245. static void clip_ear_with_edge_flag(
  246.     GLUtriangulatorObj *tobj,
  247.     tess_vertex *v,
  248.     tess_contour *contour)
  249. {
  250.     emit_triangle_with_edge_flag(tobj,v->previous,v->previous->edge_flag,
  251.         v,v->edge_flag,v->next,GL_FALSE);
  252.     v->previous->edge_flag=GL_FALSE;
  253.     /* the first in the list */
  254.     if(contour->vertices==v)
  255.     {
  256.         contour->vertices=v->next;
  257.         contour->last_vertex->next=v->next;
  258.         v->next->previous=contour->last_vertex;
  259.     }
  260.     else
  261.     /* the last ? */
  262.     if(contour->last_vertex==v)
  263.     {
  264.         contour->vertices->previous=v->previous;
  265.         v->previous->next=v->next;
  266.         contour->last_vertex=v->previous;
  267.     }
  268.     else
  269.     {
  270.         v->next->previous=v->previous;
  271.         v->previous->next=v->next;
  272.     }
  273.     free(v);
  274.     --(contour->vertex_cnt);
  275. }
  276.  
  277. static void triangulate_ccw(
  278.     GLUtriangulatorObj *tobj,
  279.     tess_contour *contour)
  280. {
  281.     tess_vertex *vertex;
  282.     GLuint vertex_cnt=contour->vertex_cnt;
  283.  
  284.     while(vertex_cnt > 3)
  285.     {
  286.         vertex=contour->vertices;
  287.         while(diagonal_ccw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  288.             tobj->error==GLU_NO_ERROR)
  289.             vertex=vertex->next;
  290.         if(tobj->error!=GLU_NO_ERROR)
  291.             return;
  292.         clip_ear(tobj,vertex->next,contour);
  293.         --vertex_cnt;
  294.     }
  295. }
  296.  
  297. static void triangulate_cw(
  298.     GLUtriangulatorObj *tobj,
  299.     tess_contour *contour)
  300. {
  301.     tess_vertex *vertex;
  302.     GLuint vertex_cnt=contour->vertex_cnt;
  303.  
  304.     while(vertex_cnt > 3)
  305.     {
  306.         vertex=contour->vertices;
  307.         while(diagonal_cw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  308.             tobj->error==GLU_NO_ERROR)
  309.             vertex=vertex->next;
  310.         if(tobj->error!=GLU_NO_ERROR)
  311.             return;
  312.         clip_ear(tobj,vertex->next,contour);
  313.         --vertex_cnt;
  314.     }
  315. }
  316.  
  317. static void triangulate_ccw_with_edge_flag(
  318.     GLUtriangulatorObj *tobj,
  319.     tess_contour *contour)
  320. {
  321.     tess_vertex *vertex;
  322.     GLuint vertex_cnt=contour->vertex_cnt;
  323.  
  324.     while(vertex_cnt > 3)
  325.     {
  326.         vertex=contour->vertices;
  327.         while(diagonal_ccw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  328.             tobj->error==GLU_NO_ERROR)
  329.             vertex=vertex->next;
  330.         if(tobj->error!=GLU_NO_ERROR)
  331.             return;
  332.         clip_ear_with_edge_flag(tobj,vertex->next,contour);
  333.         --vertex_cnt;
  334.     }
  335. }
  336.  
  337. static void triangulate_cw_with_edge_flag(
  338.     GLUtriangulatorObj *tobj,
  339.     tess_contour *contour)
  340. {
  341.     tess_vertex *vertex;
  342.     GLuint vertex_cnt=contour->vertex_cnt;
  343.  
  344.     while(vertex_cnt > 3)
  345.     {
  346.         vertex=contour->vertices;
  347.         while(diagonal_cw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  348.             tobj->error==GLU_NO_ERROR)
  349.             vertex=vertex->next;
  350.         if(tobj->error!=GLU_NO_ERROR)
  351.             return;
  352.         clip_ear_with_edge_flag(tobj,vertex->next,contour);
  353.         --vertex_cnt;
  354.     }
  355. }
  356.  
  357. void tess_tesselate(GLUtriangulatorObj *tobj)
  358. {
  359.     tess_contour *contour;
  360.  
  361.     for(contour=tobj->contours;contour!=NULL;contour=contour->next)
  362.     {
  363.         if(contour->orientation==GLU_CCW) {
  364.             triangulate_ccw(tobj,contour);
  365.         } else {
  366.             triangulate_cw(tobj,contour);
  367.         }
  368.         if(tobj->error!=GLU_NO_ERROR)
  369.             return;
  370.  
  371.         /* emit the last triangle */
  372.         emit_triangle(tobj,contour->vertices,contour->vertices->next,
  373.             contour->vertices->next->next);
  374.     }
  375. }
  376.  
  377. void tess_tesselate_with_edge_flag(GLUtriangulatorObj *tobj)
  378. {
  379.     tess_contour *contour;
  380.  
  381.     edge_flag=GL_TRUE;
  382.     /* first callback with edgeFlag set to GL_TRUE */
  383.     (tobj->callbacks.edgeFlag)(GL_TRUE);
  384.  
  385.     for(contour=tobj->contours;contour!=NULL;contour=contour->next)
  386.     {
  387.         if(contour->orientation==GLU_CCW)
  388.             triangulate_ccw_with_edge_flag(tobj,contour);
  389.         else
  390.             triangulate_cw_with_edge_flag(tobj,contour);
  391.         if(tobj->error!=GLU_NO_ERROR)
  392.             return;
  393.         /* emit the last triangle */
  394.         emit_triangle_with_edge_flag(tobj,contour->vertices,
  395.             contour->vertices->edge_flag,contour->vertices->next,
  396.             contour->vertices->next->edge_flag,contour->vertices->next->next,
  397.             contour->vertices->next->next->edge_flag);
  398.     }
  399. }
  400.  
  401. static void emit_triangle(
  402.     GLUtriangulatorObj *tobj,
  403.     tess_vertex *v1,
  404.     tess_vertex *v2,
  405.     tess_vertex *v3)
  406. {
  407.     (tobj->callbacks.begin)(GL_TRIANGLES);
  408.     (tobj->callbacks.vertex)(v1->data);
  409.     (tobj->callbacks.vertex)(v2->data);
  410.     (tobj->callbacks.vertex)(v3->data);
  411.     (tobj->callbacks.end)();
  412. }
  413.  
  414. static void emit_triangle_with_edge_flag(
  415.     GLUtriangulatorObj *tobj,
  416.     tess_vertex *v1,
  417.     GLboolean edge_flag1,
  418.     tess_vertex *v2,
  419.     GLboolean edge_flag2,
  420.     tess_vertex *v3,
  421.     GLboolean edge_flag3)
  422. {
  423.     (tobj->callbacks.begin)(GL_TRIANGLES);
  424.     if(edge_flag1!=edge_flag)
  425.     {
  426.         edge_flag = (edge_flag==GL_TRUE ? GL_FALSE : GL_TRUE);
  427.         (tobj->callbacks.edgeFlag)(edge_flag);
  428.     }
  429.     (tobj->callbacks.vertex)(v1->data);
  430.     if(edge_flag2!=edge_flag)
  431.     {
  432.         edge_flag = (edge_flag==GL_TRUE ? GL_FALSE : GL_TRUE);
  433.         (tobj->callbacks.edgeFlag)(edge_flag);
  434.     }
  435.     (tobj->callbacks.vertex)(v2->data);
  436.     if(edge_flag3!=edge_flag)
  437.     {
  438.         edge_flag = (edge_flag==GL_TRUE ? GL_FALSE : GL_TRUE);
  439.         (tobj->callbacks.edgeFlag)(edge_flag);
  440.     }
  441.     (tobj->callbacks.vertex)(v3->data);
  442.     (tobj->callbacks.end)();
  443. }
  444.